package JZ;


import java.lang.reflect.Array;
import java.util.ArrayList;

/**
 * @Classname JZ36
 * @Description // https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/ 树 一次ac
 * @Date 2021/4/21 15:02
 * @Created by yin
 */

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

public class JZ36 {
    private final ArrayList<Node> list = new ArrayList<>();

    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        dfs(root);
        int len = list.size();
        for (int i = 0; i < len; i++) {
            Node now = list.get(i);
            Node left = list.get((i + len - 1) % len);
            Node right = list.get((i + 1) % len);
            now.left = left;
            now.right= right;
        }
        return list.get(0);
    }

    public void dfs(Node node) {
        if(node == null) return;
        dfs(node.left);
        list.add(node);
        dfs(node.right);
    }
}
